package com.acme.collections;

import java.util.*;

public class IntHashMap implements Map<Integer, Integer> {

    private static final double bucketCountRelocatingFactor = 1.8;
    private static final double bucketSizeRelocatingFactor = 1.2;

    private int size;

    private int bucketsCount;
    private int bucketSize;

    private int[][] keys;
    private int[] values;

    private boolean zeroPutted;
    private int zeroValue;

    private boolean lastRelocateCount = false;

    public IntHashMap() {
        init();
    }

    private void init() {
        zeroPutted = false;
        zeroValue = 0;
        size = 0;
        bucketsCount = 13;
        bucketSize = 3;
        keys = new int[bucketsCount][bucketSize];
        values = new int[bucketsCount * bucketSize];
    }


    private int putInt(int key, int value) {
        if (key == 0) {
            return putZero(value);
        }

        Integer result = insertInt(key, value, keys, values);
        if (result == null) {
            relocateMemory();
            result = insertInt(key, value, keys, values);
        }
        size++;
        return result;
    }

    private static Integer insertInt(int key, int value, int[][] keysArray, int valuesArray[]) {
        int bucketIndex = getBacketIndex(key, keysArray.length);

        int bucketSize = keysArray[bucketIndex].length;

        for (int k = 0; k < bucketSize; k++) {

            int oldKey = keysArray[bucketIndex][k];
            if (oldKey == 0) {
                keysArray[bucketIndex][k] = key;
                valuesArray[bucketIndex * bucketSize + k] = value;
                return value;
            }
            if (oldKey == key) {
                return valuesArray[bucketIndex * bucketSize + k];
            }
        }

        return null;
    }

    private int putZero(int value) {
        if (zeroPutted) {
            return zeroValue;
        } else {
            zeroValue = value;
            zeroPutted = true;
            size++;
            return value;
        }
    }

    private Integer getInt(int key) {
        if (key == 0) {
            if (zeroPutted) {
                return zeroValue;
            } else {
                return null;
            }
        }

        int bucket = getBacketIndex(key, bucketsCount);

        for (int k = 0; k < bucketSize; k++) {

            int oldKey = keys[bucket][k];

            if (oldKey == key) {
                return values[bucket * bucketSize + k];
            }
        }

        return null;
    }

    @Override
    public int size() {
        return size;
    }

    private void relocateMemory() {

        int nBucketCount = bucketsCount;
        int nBucketSize = bucketSize;
        int nCapacity;

        if (lastRelocateCount) {
            nBucketCount = (int) Math.round(nBucketCount * bucketCountRelocatingFactor);
        } else {
            nBucketSize = (int) Math.round(nBucketSize * bucketSizeRelocatingFactor);
        }
        lastRelocateCount = !lastRelocateCount;

        nCapacity = nBucketCount * nBucketSize;

        int[] nValues = new int[nCapacity];
        int[][] nKeys = new int[nBucketCount][nBucketSize];

        for (int i = 0; i < keys.length; i++) {
            int[] bucket = keys[i];
            for (int j = 0; j < bucket.length; j++) {
                int key = bucket[j];

                if (key == 0) continue;

                int value = values[bucketSize * i + j];

                insertInt(key, value, nKeys, nValues);
            }
        }


        bucketsCount = nBucketCount;
        bucketSize = nBucketSize;
        keys = nKeys;
        values = nValues;
    }

    private static int getBacketIndex(int key, int length) {
        return key % length;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Integer get(Object key) {
        if (key instanceof Integer) {
            return getInt((Integer) key);
        }
        throw new UnsupportedOperationException();
    }

    @Override
    public Integer put(Integer key, Integer value) {
        return putInt(key, value);
    }

    public int put(int key, int value) {
        return putInt(key, value);
    }

    @Override
    public void clear() {
        init();
    }

    @Override
    public boolean containsKey(Object key) {

        if (!(key instanceof Integer)) return false;

        int iKey = (Integer) key;
        int bucketIndex = getBacketIndex((Integer) key, keys.length);

        int[] bucket = keys[bucketIndex];
        for (int aBucket : bucket) {
            if (aBucket == iKey) return true;
        }
        return false;
    }

    @Override
    public boolean containsValue(Object value) {

        if (!(value instanceof Integer)) return false;

        int iValue = (Integer) value;

        for (int v : values) {
            if (v == iValue) return true;
        }
        return false;
    }

    @Override
    public Integer remove(Object key) {

        if (!(key instanceof Integer)) throw new IllegalArgumentException("Integer requires as key");
        int iKey = (Integer) key;

        int bucketIndex = getBacketIndex(iKey, keys.length);
        int[] bucket = keys[bucketIndex];

        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] == iKey) {
                bucket[i] = 0;
                return values[bucketSize * bucketIndex + i];
            }
        }

        return null;
    }

    @Override
    public void putAll(Map<? extends Integer, ? extends Integer> m) {
        for (Entry<? extends Integer, ? extends Integer> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public Set<Integer> keySet() {
        Set<Integer> set = new HashSet<Integer>();
        for (int[] bucket : keys) {
            for (int key : bucket) {
                set.add(key);
            }
        }
        return set;
    }

    @Override
    public Collection<Integer> values() {
        Collection<Integer> collection = new ArrayList<Integer>();
        for (int value : values) {
            collection.add(value);
        }
        return collection;
    }

    @Override
    public Set<Entry<Integer, Integer>> entrySet() {
        Set<Entry<Integer, Integer>> set = new HashSet<Entry<Integer, Integer>>();
        for (int i = 0; i < keys.length; i++) {
            for (int j = 0; j < keys[i].length; j++) {
                set.add(new AbstractMap.SimpleEntry<Integer, Integer>(keys[i][j], values[i * keys[i].length + j]));
            }
        }
        return set;
    }
}
